package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class ContainsDuplicate {

	static String s;

	public static void main(String[] args) {
		ContainsDuplicate object = new ContainsDuplicate();
		int[] nums = { -1, 2147483647 };
		System.out.println(object.containsNearbyAlmostDuplicate(nums, 1, 1));
	}

	// TLE了
	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
		if (nums == null || nums.length <= 1) {
			return false;
		}
		if (k < 1 || t < 0) {
			return false;
		}
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			min = Math.min(min, nums[i]);
			max = Math.max(max, nums[i]);
		}
		// 超时了，时间复杂度为O(n * k)
		HashMap<Integer, Long> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			int less = Math.max(0, i - k);
			int more = Math.min(nums.length - 1, i + k);
			System.out.println("less： " + less + " more: " + more);
			for (int key = less; key <= more; key++) {
				if (map.containsKey(key)) {
					if (Math.abs(map.get(key) - nums[i]) <= t) {
						return true;
					}
				}
			}
			map.put(i, new Long(nums[i]));
		}
		return false;
	}

	public boolean containsNearbyAlmostDuplicate2(int[] nums, int k, int t) {
		if (nums == null || nums.length <= 1) {
			return false;
		}
		if (k < 1 || t < 0) {
			return false;
		}

		TreeSet<Long> set = new TreeSet<>();
		
		for(int i = 0; i < nums.length; i++){
			
//			其实只需要一个
//			Long floor = set.floor((long)nums[i] + t);
//            if (floor != null && floor + t >= nums[i]) {
//                return true;
//            }
//            
			//Returns the greatest element in this set less than or equal to the given element
			Long ceiling = set.floor((long)nums[i] + t);
			//Returns the least element in this set greater than or equal to the given element
			Long floor = set.ceiling((long)nums[i] - t);
			
			if(ceiling != null && ceiling >= nums[i]
					|| (floor != null && floor <= nums[i])){
				return true;
			}
			set.add((long)nums[i]);
			
			//注意，此时需要将下标超期的移除
			//因为i, j(i < j)满足的话，那么我们之后遍历到j的时候一定会找到i
			//所以我们只用移除小于下标的超过k的元素
			if(i >= k){
				set.remove((long)nums[i - k]);
			}
		}
		return false;
	}
	
	
	//map和桶排序
	public boolean containsNearbyAlmostDuplicate3(int[] nums, int k, int t) {
		if (k < 1 || t < 0)
			return false;
		Map<Long, Long> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			//将nums[i]转换为正数
			long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
			//获取桶的id
			//由于桶的大小为t + 1，所以满足条件的一定是当前桶或者相邻桶
			long bucket = remappedNum / ((long) t + 1);
			if (map.containsKey(bucket)
					|| (map.containsKey(bucket - 1) && remappedNum
							- map.get(bucket - 1) <= t)
					|| (map.containsKey(bucket + 1) && map.get(bucket + 1)
							- remappedNum <= t)){
				return true;
			}
			//当大于k时的处理
			if (map.entrySet().size() >= k) {
				long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE)
						/ ((long) t + 1);
				map.remove(lastBucket);
			}
			map.put(bucket, remappedNum);
		}
		return false;
	}
}
